Week 4
Last Time
-
Last time we looked at numbers and how we might search them and sort them, with algorithms like:
-
linear search
-
binary search
-
bubble sort
-
selection sort
-
insertion sort
-
merge sort
-
-
We started using basic terms to describe running time (in units of steps taken), like:
-
n2
-
n log n
-
n
-
log n
-
1
-
…
-
-
The notation for running time includes:
-
O, worst-case running time
-
Ω, best-case running time
-
Θ, if both of those are the same
-
Strings
-
Now we’ll take a closer look at strings and how they are actually stored by the computer.
-
Let’s look at
compare0.c:#include <cs50.h> #include <stdio.h> int main(void) { printf("s: "); string s = get_string(); printf("t: "); string t = get_string(); if (s == t) { printf("same\n"); } else { printf("different\n"); } }-
It looks like this program takes two strings from the user and compares them.
-
But it doesn’t work, when we put in two strings that look the same.
-
-
Hm, mysterious. Let’s try to copy the string:
#include <cs50.h> #include <ctype.h> #include <stdio.h> #include <string.h> int main(void) { printf("s: "); string s = get_string(); if (s == NULL) { return 1; } string t = s; if (strlen(t) > 0) { t[0] = toupper(t[0]); } printf("s: %s\n", s); printf("t: %s\n", t); return 0; }-
Now we’re getting a string
sfrom the user, copying it to a string calledt, and then making the first letter oftuppercase. -
But when we run the program, it again doesn’t behave like we might expect. Both
sandtare capitalized!
-
-
Another example we can look at:
#include <stdio.h> void swap(int a, int b); int main(void) { int x = 1; int y = 2; printf("x is %i\n", x); printf("y is %i\n", y); printf("Swapping...\n"); swap(x, y); printf("Swapped.\n"); printf("x is %i\n", x); printf("y is %i\n", y); } void swap(int a, int b) { int tmp = a; a = b; b = tmp; }-
We have a function called
swapthat’s supposed to take two values,aandb, and swaps them. It takesa, puts the value into a temporary variable calledtmp, and then stores the value ofbintoa. Then the value oftmp, which is the originala, is stored intob. -
But when we run this program, too, it doesn’t swap the values of
xandyinmain.
-
-
So we open our debugger, and step over each line of our program:
-
Stepping into the
swapfunction, we see thataandbare indeed the right values. But when we get back tomain,xandyare still the same. -
It turns out that programs are given memory by the operating system, and areas of memory are set aside in a fairly standard way:
-
If we think about memory as a rectangle, a grid of bytes, each area (comprised of many many bytes) can be labeled as above.
-
At the top is a chunk called "text," and that’s actually where the machine code for your program is put in memory.
-
Below that is the data, or variables, your program is using.
-
-
Then we have something we call the stack. The "bottom" of our computer’s memory, or the area with high addresses, is used for functions. In fact, for our C programs, the very bottom of the stack contains a chunk of memory for our
mainfunction, with any local variables or arguments:-
Then on top, the next function called, such as
swap, will have its own chunk of memory.
-
-
And we can realize that each block, or byte, is individually addressed and stores some value, which explains what we saw earlier:
-
swaphas its arguments passed in as copies.
-
-
And once
swapreturns, its part of the stack is marked as usable (since it’s returned), somainstill sees the samexandy. -
And when we were comparing
sandtearlier, we were actually comparing two memory addresses. When we callget_string(), we’re actually storing the characters of the string somewhere else in memory (since we don’t know how big the string will be). For example, if we calledget_stringand the user typed inZamyla, the characters might be stored in memory starting at address123. (Recall that a string is just an array of characters, each one in a byte in a consecutive set of bytes.) So ourswill have the value123. -
And when we call
get_stringagain for another string,t, whatever the user types in will be stored somewhere else in memory, regardless of its contents. Sotmight have the value234if the second string was stored starting at byte234. (And this address is "dynamically allocated" by a C library, since we don’t necessarily know ahead of time how big the string will be.) -
When we tried to capitalize just one string, too, we were just setting
tto the address of the stringswas pointing to: -
In fact, we can think of both
sandtas "pointers" to values that we care about. So in the end, what we knew as astringtype was really just a pointer to a character (the start of a "string"). (And recall that we recognize the end of a string by the\0character, so we don’t need to store the length or the ending address.) -
So how might we compare a string?
#include <cs50.h> #include <stdio.h> #include <string.h> int main(void) { printf("s: "); char *s = get_string(); printf("t: "); char *t = get_string(); if (s != NULL && t != NULL) { if (strcmp(s, t) == 0) { printf("same\n"); } else { printf("different\n"); } } }-
Now that we know what
get_stringactually returns, we can set the type of our variablestochar *, or a pointer to a character. (And indeed the CS50 Library has just been mapping all mentions ofstringtochar *this whole time!) -
Turns out, there exists a library function called
strcmpthat compares strings, and returns0if they’re the same. Andstrcmpprobably does that with a loop looking at theith character in each string, comparing them one at a time.
-
-
To make a copy of a string, we do something a little fancier:
#include <cs50.h> #include <ctype.h> #include <stdio.h> #include <string.h> int main(void) { printf("s: "); char *s = get_string(); if (s == NULL) { return 1; } char *t = malloc((strlen(s) + 1) * sizeof(char)); if (t == NULL) { return 1; } for (int i = 0, n = strlen(s); i <= n; i++) { t[i] = s[i]; } if (strlen(t) > 0) { t[0] = toupper(t[0]); } printf("s: %s\n", s); printf("t: %s\n", t); free(t); return 0; }-
We get
sas usual, but then fortwe use another C library function calledmalloc, which allocates some memory for us to use. The amount of memory we ask for is the length ofs(plus 1 for\0to end the string), times the size of a single character. And ifmallocreturnsNULLfort, that means something went wrong (perhaps we ran out of memory), so our program too needs to check for that and return an error if so. -
Now we can deliberately go through the entire string, and one past the end of the string, to copy the
\0character. Then we’ll have a copy ofsint, and changing something intwill no longer changes. -
Finally, at the end of our program, we should make the habit of calling
freeon our manually allocated memory, which marks it as usable again.
-
-
We can also fix our
swap:#include <stdio.h> void swap(int *a, int *b); int main(void) { int x = 1; int y = 2; printf("x is %i\n", x); printf("y is %i\n", y); printf("Swapping...\n"); swap(&x, &y); printf("Swapped!\n"); printf("x is %i\n", x); printf("y is %i\n", y); } void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; }-
Now we’re passing in pointers to our
mainfunction’sxandy, and swapping their values directly. The syntax to get an address of variable is with&, and to go the other way and get the value at some address is with a*. (Not to be confused with declaring a pointer, which would be usingchar *orint *to say "I would like a new variable that stores a pointer to acharorint.")
-
-
So now our
swapfunction gets the addresses ofmain'sxandy, and can swap them (with the help of a temporary variable): -
Now that we know the basics of pointers, we can do even more with them:
#include <cs50.h> #include <stdio.h> #include <string.h> int main(void) { // get line of text char *s = get_string(); if (s == NULL) { return 1; } // print string, one character per line for (int i = 0, n = strlen(s); i < n; i++) { printf("%c\n", *(s+i)); } }-
This program just prints a string, one character at a time. Since
sis a pointer to the first character (the address of the first character), addingito it means we’ll get the addressicharacters down. For example, if the first character started at address123, the third character (2 down) will be at address125. And so we can use our*notation to access the character at that address. (And we’ve useds[i]before, which actually means the exact same thing. The C language has this feature as "syntactic sugar" which means that it’s convenient and easy to read, but not necessary to have, since we can express it otherwise.)
-
-
At the same time, it’s easier to write buggy code:
int main(void) { int *x; int *y; x = malloc(sizeof(int)); *x = 42; *y = 13; y = x; *y = 13; }-
We allocate memory that can hold an
int, and pointxto it. Then we set that to42with*x = 42, since we got a chunk of memory to use. -
But the next line will not work and even crash our program, because
yis pointing to … somewhere in memory, and we’re just changing that random value to13. When we declare a variable, we have some area of memory allocated to it, but the value inside is some random garbage value.
-
-
We’ll watch a quick animation about pointers.
-
Another problem is memory leaks. If we allocate a lot of memory and not call
free, or mark it as usable again, then our computer has less and less memory. -
valgrindis another command-line tool that we can use to check for these memory leaks. -
Let’s run:
// http://valgrind.org/docs/manual/quick-start.html#quick-start.prepare. #include <stdlib.h> void f(void) { int *x = malloc(10 * sizeof(int)); x[10] = 0; } int main(void) { f(); return 0; }-
We’re going to call some function
fthat allocates memory for 10 integers, but never frees it.falso tries to access the "10"th element of that array of integers, but since we start counting at0,x[10]is actually the 11th element, which we did not allocate, and so actually holds something else in memory that could be important. -
If we save this as
memory.candmake memory, we can runvalgrind --leak-check=full ./memory. -
Then we’ll see something like:
Invalid write of size 4 at 0x4005FF: f (memory.c:21) by 0x400623: main (memory.c:26) ... 40 bytes in 1 blocks are definitely lost in loss record 1 of 1 at 0x4C2AB80: malloc in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) by 0x4005F6: f (memory.c:20) by 0x400623: main (memory.c:26) -
We see that the output is a little hard to read, but ultimately the source of these errors come from some lines in
memory.c. -
We can fix this program by changing
f:... void f(void) { int *x = malloc(10 * sizeof(int)); x[9] = 0; free(x); } ...
-
-
If we look back to our layout of memory, we see another area called the heap, and that is where these
malloced chunks of memory come from: -
The stack contains memory that disappears as functions return, but the heap contains memory that will be usable until we
freeit. -
And if we look at the arrows, we see the implication that they might collide if we use too much memory in the heap and too much memory in the stack, as they grow in opposite directions.
-
"Stack overflow" is the term for a stack that has grown too large, perhaps if we have a recursive function that calls itself too many times.
-
"Heap overflow" is the term for a heap that is too large, perhaps if we called
mallocfor large chunks of memory without ever callingfree. -
"Buffer overflow" is the overarching term for when too much data is placed into a finite amount of allocated space.
#include <string.h> void foo(char *bar) { char c[12]; memcpy(c, bar, strlen(bar)); } int main(int argc, char *argv[]) { foo(argv[1]); }-
We see buffer overflow in a program like this.
maincalls the functionfooand passes in whatever the command-line argument to it is.foothen copies it to achararrayc, butccan only hold 12 characters. (memcpycopies frombarintoc, for as many bytes asstrlen(bar). And our friendlymanpages tells us this and more.) So if the command-line argument is too long, then the rest it will "overflow" and be written to the chunk of memory right after what’s allocated toc.
-
-
And since
cis a static variable, it will be on the stack, which means that whatever the user passed in as a command-line argument will be written to the stack, and possibly executed as machine code!